#include <iostream>
#include <vector>

template <class T>
class ListNode // 可以初始化节点值 初始化指针为nullptr
{
public:
    T val;
    ListNode<T>* next;
    /* data */
public:
    ListNode(void) : next(nullptr){}
    ListNode(T value) : next(nullptr), val(value){}

    ~ListNode(){}
};


template<class T>
class LinkedList
{
public:
    ListNode<T>* L = nullptr;          // 头指针
    ListNode<T>* tail = nullptr;       // 尾指针
    int size;                       // 链表的大小
public:
    /*
        仅初始化头节点
    */
    LinkedList()
    {
        L = new ListNode<T>();
        tail = L;
        this->size = 0;
    }
    /*
        初始化头节点
        按照nums的顺序初始化链表
    */
    LinkedList(T nums[], int len)
    {
        L = new ListNode<T>;
        tail = L;
        this->size = 0;
        for(int i=0; i<len; i++)
        {
            tail->next = new ListNode<T>(nums[i]);
            tail = tail->next;
            this->size++;
        }
    }
    /*
        销毁所有内存空间
    */
    ~LinkedList()
    {
        ListNode<T>* cur = L;
        while(cur!=nullptr)
        {
            ListNode<T>* next = cur->next;
            delete cur;
            cur = next;
        }

        delete L;
        L = nullptr;
    };
    /*
        头插法插入 O(1)
    */
    void insertHead(T val) 
    {
        ListNode<T>* newnode = new ListNode<T>(val);
        newnode->next = L->next;
        L->next = newnode;  
        this->size++;
    }
    /*
        尾插法插入 由于包含尾指针 O(1)
    */
    void insertTail(T val)
    {
        tail->next = new ListNode<T>(val);
        tail = tail->next;
        this->size++;
    }
    /*
        查询位于pos位置的元素的值
    */
    int at(int pos)
    {
        ListNode<T>* p = L->next;
        int i=0;
        while(i<pos)
        {
            p = p->next;
            i++;
        }
        return p->val;
    }

    void insertAtpos(int pos, T value)
    {
        ListNode<T>* p = L->next;
        ListNode<T>* last = L;
        for(int i=0;i<pos;i++)
        {
            p = p->next;
            last = last->next;
        }

        last->next = new ListNode<T>(value);
        last->next->next = p;

    }

    void updateAtpos(int pos, T value)
    {
        ListNode<T>* p = L->next;
        for(int i=0; i<pos; i++)
        {
            p = p->next;
        }

        p->val = value;
    }

 
    /*
        销毁pos位置的节点
    */
    void deleteNode(int pos)
    {
        ListNode<T>* last = L;
        ListNode<T>* p = L->next;
        int i=0;
        while(i<pos)
        {
            p = p->next;
            last = last->next;
            i++;
        }
        last->next = p->next;
        delete p;
        p = nullptr;
        this->size--;
    }



    /*
        销毁所有值为value的节点
    */
    void deleteNodeAsVal(T value)
    {
        ListNode<T>* last = L;
        ListNode<T>* p = L->next;
        while(p!=nullptr)
        {
            if(p->val == value)
            {
                last->next = p->next;
                delete p;
                p = last->next;
                this->size--;
            }
            else
            {
                p = p->next;
                last  = last->next;
            }
        }

    }
    /*
        返回链表的长度
    */
    int length(void)
    {
        return this->size;
    }

    /*
        按顺序打印链表
    */
    void printList(void)
    {
        ListNode<T>* p = L->next;
        while(p!=nullptr)
        {
            std::cout << p->val << " ";
            p = p->next;
        }
        printf("\n");
    }


};




int main(){

    int nums[] = {12, 34, 21, 55, 90, 4, 6, 99};
    int len = sizeof(nums) / sizeof(nums[0]);
    
    LinkedList<int>* L = new LinkedList<int>(nums, len);

    L->insertTail(100);
    L->insertTail(200);
    L->insertTail(300);

    L->insertHead(1);
    L->insertHead(1);
    L->insertHead(1);

    L->printList();
    
    L->deleteNode(L->length()-3);
    L->printList();

    L->deleteNodeAsVal(12);
    L->printList();

    L->insertAtpos(5, 0);
    L->printList();

    L->updateAtpos(5, 11);
    L->printList();

    delete L;
    L = nullptr;
    
    
    return 0;
}